Over the past few years, a fair number of distributed stream processing systems have matured into a product or an open-source offering. This has led to a rapid adoption of the technology into real application domains such as financial markets, health-care and telecommunications. However, it has also resulted in real world stream processing applications that are far more complex and compute intensive, but strive for more efficient performance. In many such applications, performance is hard to achieve because of a small number of characteristically complex operators that bottleneck the performance of the entire application. In scenarios where such operators are stateless, a solution is to execute multiple copies of such an operator in parallel. However, when such bottleneck operators are stateful, enabling parallelization to avoid the bottleneck is difficult. An example of this is shown in FIG. 1, which will be discussed in further detail later.
Although a handful of stateful operators (e.g. SUM, AVG over a window of tuples) can be parallelized without the use of shared state, enabling parallelization requires the existence of a state sharing mechanism. Having a shared state makes it difficult to implement a parallel version of a stateful operator and difficult to incur additional overheads in the form of accesses to shared state and synchronization constructs. The complex enabling mechanisms coupled with the additional overheads make it novel to parallelize and to create a suitable parallelization for stateful operators.